package com.dzu.medium;

import java.util.*;

/**
 * @author ZhaoDong
 * @date 2022/10/26 10:12
 * @description 522. 最长特殊序列 II
 */
public class Test522 {

    public static void main(String[] args) {
        System.out.println(findLUSlength(new String[]{"aabbcc", "aabbcc","bc"}));
    }

    // owner
    public static int findLUSlength(String[] strs) {

        HashMap<String, Integer> map = new HashMap<>();

        for (String str : strs) {
            map.put(str, map.getOrDefault(str, 0) + 1);
        }

        int max = -1;

        List<String> keyList = new ArrayList<>(map.keySet());

        keyList.sort(Comparator.comparingInt(String::length).reversed());

        List<String> list = new ArrayList<>();

        for (String key : keyList) {
            if (map.get(key) > 1) {
                list.add(key);
                continue;
            }
            boolean flag = false;
            for (String str : list) {
                int temp = 0;
                int start = 0;
                while (temp < str.length() && start < key.length()) {

                    if (str.charAt(temp) == key.charAt(start)) {
                        start++;
                    }
                    temp++;

                }
                if (start == key.length()) {
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                max = Math.max(max, key.length());
            }
        }
        return max;
    }


    // 宫水三叶
    public int findLUSlength2(String[] strs) {
        int n = strs.length, ans = -1;
        for (int i = 0; i < n; i++) {
            if (strs[i].length() <= ans) continue;
            boolean ok = true;
            for (int j = 0; j < n && ok; j++) {
                if (i == j) continue;
                if (check(strs[i], strs[j])) ok = false;
            }
            if (ok) ans = strs[i].length();
        }
        return ans;
    }


    boolean check(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (m < n) return false;
        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = s1.charAt(i - 1) == s2.charAt(j - 1) ? f[i - 1][j - 1] + 1 : f[i - 1][j - 1];
                f[i][j] = Math.max(f[i][j], f[i - 1][j]);
                f[i][j] = Math.max(f[i][j], f[i][j - 1]);
                if (f[i][j] == n) return true;
            }
        }
        return false;
    }


}
